/**
 * 定义树的节点
 * @param {*} key 
 */
function Node(key) {
  this.key = key;  // 节点值
  this.left = null;  // 左侧子节点
  this.right = null; // 右侧子节点
}

/**
 * 定义二叉树的构造方法
 * @param {*} compareFn(a,b) 接受一个函数，用于自定义节点（键）的比较.
 *   compareFn会对a和b进行比较，如果满足a>b返回1；a==b返回0；a<b返回-1；
 */
function BinarySearchTree(compareFn) {
  this.compareFn = compareFn || this.defaultCompare;
  this.root = null;
}
// 如果满足a>b返回1；a==b返回0；a<b返回 -1；
BinarySearchTree.prototype.defaultCompare = function (a, b) {
  if (a === b) return 0;
  return a < b ? -1 : 1;
}
// + insert(key)：向树中插入一个新的键。
BinarySearchTree.prototype.insert = function (key) {
  const that = this;
  const newNode = new Node(key);
  if (this.root == null) {
    this.root = newNode;
  } else {
    inserNode(this.root, newNode);
  }
  // 需要递归，这里构造辅助函数
  function inserNode(node, newNode) {
    // key要小于当前节点，应该找左子树
    if (that.compareFn(newNode.key, node.key) === -1) {
      // 刚好左子树为空，正好占用
      if (node.left == null) {
        node.left = newNode;
      } else {
        inserNode(node.left, newNode);
      }
    } else {
      if (node.right == null) {
        node.right = newNode;
      } else {
        inserNode(node.right, newNode);
      }
    }
  }
}

// + search(key)：在树中查找一个键。如果节点存在，则返回true；如果不存在，则返回false。
BinarySearchTree.prototype.search = function (key) {
  const that = this;
  return searchNode(this.root, key);

  function searchNode(node, key) {
    if (node == null) return false;
    if (that.compareFn(key, node.key) == -1) {
      return searchNode(node.left, key);
    } else if (that.compareFn(key, node.key) == 1) {
      return searchNode(node.right, key);
    }
    return true;

  }
}
// + inOrderTraverse(callback)：通过中序遍历方式遍历所有节点。
BinarySearchTree.prototype.inOrderTraverse = function (callback) {
  inOrderTraverseNode(this.root, callback);
  // 必须递归，辅助函数
  function inOrderTraverseNode(node, callback) {
    if (node != null) {
      // 从左边进行遍历
      inOrderTraverseNode(node.left, callback);
      // 处理当前节点
      callback(node.key);
      // 从右边开始
      inOrderTraverseNode(node.right, callback);
    }
  }
}

// + preOrderTraverse(callback)：通过先序遍历方式遍历所有节点。
BinarySearchTree.prototype.preOrderTraverse = function (callback) {
  preOrderTraverseNode(this.root, callback);

  // 用于递归的辅助方法
  function preOrderTraverseNode(node, callback) {
    if (node != null) {
      // 先打印当前,再左再右
      callback(node.key);
      preOrderTraverseNode(node.left, callback);
      preOrderTraverseNode(node.right, callback);
    }
  }
}

// + postOrderTraverse()：通过后序遍历方式遍历所有节点。
BinarySearchTree.prototype.postOrderTraverse = function (callback) {
  postOrderTraverseNode(this.root, callback);

  // 用于递归的辅助方法
  function postOrderTraverseNode(node, callback) {
    if (node != null) {
      postOrderTraverseNode(node.left, callback);
      postOrderTraverseNode(node.right, callback);
      callback(node.key);
    }
  }
}

// + min()：返回树中最小的值/键。
BinarySearchTree.prototype.min = function () {
  return minNode(this.root);

  function minNode(node) {
    let currnt = node;
    // 直接找寻左子节点就是最小值
    while (node != null & node.left != null) {
      currnt = currnt.left;
    }
    return currnt;
  }
}
// + max()：返回树中最大的值/键。
BinarySearchTree.prototype.max = function () {
  return maxNode(this.root);

  function maxNode(node) {
    let currnt = node;
    while (node != null && node.right != null) {
      currnt = node.right;
    }
    return currnt;
  }
}
// + remove(key)：从树中移除某个键。
BinarySearchTree.prototype.remove = function (key) {
  const that = this;
  this.root = removeNode(this.root, key);

  // 递归辅助函数
  function removeNode(node, key) {
    if (node == null) return null;
    // 去左子树找
    if (that.compareFn(key, node.key) === -1) {
      node.left = removeNode(node.left, key);
      return node;
    } else if (that.compareFn(key, node.key) === 1) {
      node.right = removeNode(node.right, key);
      return node;
      // 相等。
    } else {
      // 1. 如果是叶子节点，直接删除
      if (node.left == null && node.right == null) {
        node = null;
        return node;
      }
      // 2. 如果只有左子树或者右子树
      if (node.right == null) {
        node = node.left;
        return node;
      } else if (node.left == null) {
        node = node.right;
        return node;
      }
      // 3. 如果同时存在两个子树
      //  3.1 规律是从左子树找到最大值的键替换当前键
      //  3.2 或者从右子树找到最小值的键替换当前键
      const minNodeRight = that.min(node.right);
      node.key = minNodeRight.key;
      // 删除这个键
      that.removeNode(node.right, minNodeRight.key);
      return node;
    }
  }
}

module.exports = BinarySearchTree;